package zw_601_700.zw_696_计数二进制子串;

class Solution {

    public static void main(String[] args) {
        String s = "10101";
        int count = countBinarySubstrings(s);
        System.out.println(count);

    }

    /**
     * 方法一：按字符分组
     * 思路与算法
     * 我们可以将字符串 s 按照 0 和 1 的连续段分组，存在 counts 数组中，例如 s=00111011，可以得到这样的 counts 数组：counts={2,3,1,2}。
     * 这里 counts 数组中两个相邻的数一定代表的是两种不同的字符。
     * 假设 counts 数组中两个相邻的数字为 u 或者 v，它们对应着 u 个 0 和 v 个 1，或者 u 个 1 和 v 个 0。
     * 它们能组成的满足条件的子串数目为min{u,v}，即一对相邻的数字对答案的贡献。
     * 我们只要遍历所有相邻的数对，求它们的贡献总和，即可得到答案。
     *
     * @param s
     * @return
     */
    public static int countBinarySubstrings(String s) {
        int ptr = 0, n = s.length(), last = 0, ans = 0;
        while (ptr < n) {
            char c = s.charAt(ptr);
            int count = 0;
            while (ptr < n && s.charAt(ptr) == c) {
                ++ptr;
                ++count;
            }
            ans += Math.min(count, last);
            last = count;
        }
        return ans;
    }


    /**
     * https://leetcode.cn/problems/count-binary-substrings/solution/count-binary-substrings-by-ikaruga/
     *
     * @param s
     * @return
     */
//    public static int countBinarySubstrings(String s) {
//        int ans = 0;
//        char last = '-';
//        int cnt_pre = 0, cnt_cur = 0;
//        s += '-';
//        char[] chars = s.toCharArray();
//        for (char c : chars) {
//            if (last != c) {
//                last = c;
//                ans += Math.min(cnt_pre, cnt_cur);
//                cnt_pre = cnt_cur;
//                cnt_cur = 0;
//            }
//            cnt_cur++;
//        }
//        return ans;
//    }
}

